package com.lw.leetcode.sort.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer II 115. 重建序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/12 21:16
 */
public class SequenceReconstruction {


    public static void main(String[] args) {
        SequenceReconstruction test = new SequenceReconstruction();

        // true;
//        int[] arr = {4, 1, 2, 3};
//        List<List<Integer>> list = new ArrayList<>();
//        list.add(Arrays.asList(1, 2));
//        list.add(Arrays.asList(1, 3));
//        list.add(Arrays.asList(2, 3));
//        list.add(Arrays.asList(4, 1, 2));

        // false;
//        int[] arr = {1, 2};
//        List<List<Integer>> list = new ArrayList<>();
//        list.add(Arrays.asList(1, 2));
//        list.add(Arrays.asList(2, 1));

        // false;
        int[] arr = {1};
        List<List<Integer>> list = new ArrayList<>();
        list.add(Arrays.asList(2));

        boolean b = test.sequenceReconstruction(arr, list);
        System.out.println(b);
    }

    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        if (seqs == null || seqs.size() == 0) {
            return false;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        int length = org.length;
        int[] counts = new int[length + 1];

        for (List<Integer> seq : seqs) {
            int size = seq.size();
            if (size == 1) {
                int a = seq.get(0);
                if (a < 1 || a > length) {
                    return false;
                }
            }
            for (int i = 1; i < size; i++) {
                int a = seq.get(i - 1);
                int b = seq.get(i);
                if (a == b || a < 1 || b < 1 || a > length || b > length) {
                    return false;
                }
                map.computeIfAbsent(a, v -> new ArrayList<>()).add(b);
                counts[b]++;
            }
        }
        boolean flag = false;
        for (int i = 1; i <= length; i++) {
            int count = counts[i];
            if (count == 0) {
                flag = true;
                if (org[0] != i) {
                    return false;
                }
            }
        }
        if (!flag) {
            return false;
        }
        int index = 1;
        while (index < length) {
            List<Integer> list = map.get(org[index - 1]);
            flag = false;
            for (Integer v : list) {
                counts[v]--;
                if (counts[v] == 0) {
                    flag = true;
                    if (org[index] != v) {
                        return false;
                    }
                }
            }

            if (!flag) {
                return false;
            }
            index++;
        }
        return 0 == counts[org[length - 1]];
    }

    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        if (seqs == null || seqs.length == 0) {
            return false;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        int length = org.length;
        int[] counts = new int[length + 1];

        for (int[] seq : seqs) {
            int size = seq.length;
            if (size == 1) {
                int a = seq[0];
                if (a < 1 || a > length) {
                    return false;
                }
            }
            for (int i = 1; i < size; i++) {
                int a = seq[i - 1];
                int b = seq[i];
                if (a == b || a < 1 || b < 1 || a > length || b > length) {
                    return false;
                }
                map.computeIfAbsent(a, v -> new ArrayList<>()).add(b);
                counts[b]++;
            }
        }
        boolean flag = false;
        for (int i = 1; i <= length; i++) {
            int count = counts[i];
            if (count == 0) {
                flag = true;
                if (org[0] != i) {
                    return false;
                }
            }
        }
        if (!flag) {
            return false;
        }
        int index = 1;
        while (index < length) {
            List<Integer> list = map.get(org[index - 1]);
            flag = false;
            for (Integer v : list) {
                counts[v]--;
                if (counts[v] == 0) {
                    flag = true;
                    if (org[index] != v) {
                        return false;
                    }
                }
            }

            if (!flag) {
                return false;
            }
            index++;
        }
        return 0 == counts[org[length - 1]];
    }

}
